/**
 * DATABASE SYSTEMS IMPLEMENTATION - PROJECT 2
 * STAGE 2 - CODE SUBMISSION
 * 
 * AUTHORS:
 * NEHA SRIVASTAVA NS2724
 * TANAY TANDON  TT2382
 * 
 * 
 * DEPARTMENT OF COMPUTER SCIENCE,
 * COLUMBIA UNIVERSITY, 2011
 */
package algorithm;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Properties;
import java.util.Set;


/**
 * @author Neha
 */

public class Main {

	/**
	 * @param mainTerms: list of terms
	 * @param k: number of terms
	 * @param numOfSubset: number of possible subsets
	 * @param A: Array of subsets 
	 */
	
	static ArrayList<double[]> productivities = new ArrayList<double[]>();
	static double r;
	static double t;
	static double l;
	static double m;
	static double a;
	static double f;
	static int k=0;
	static int numOfSubset=0;
	static double[] currentArray;
	public static HashMap<Double,Integer> lookUpMap= new HashMap<Double,Integer>();
	static boolean leftMostPlan=false;
	
	public Node[] setA(double[] elements, int numOfSubset)
	{
		/**Generating all possible combinations and populating
		 * the A array
		 */
		int[] indices;		
		int count=0;
		Node A[]=new Node[numOfSubset] ;
		for(int j=1; j<=elements.length; j++)
		{
				CombinationGenerator x= new CombinationGenerator (elements.length, j);
				ArrayList<Double> combination= new ArrayList<Double>();
				
				while(x.hasMore())
				{
					combination.clear();
					A[count]=new Node();
					indices= x.getNext();
					for(int i=0; i<indices.length; i++)
					{
						combination.add(elements[indices[i]]);
						A[count].terms.add(elements[indices[i]]);
						
					}
					A[count].initNameHash();
					count++;
				}
		}
		return A;
	}
	
	public static boolean cMetricComparator(Node s, double _s1)
	{
		/**
		 * The above method takes as input the node S and the first term of s1.
		 * It returns true if the c-metric of _s is dominated by the c-metric of 
		 * first term of s.
		 */
		double term1_1=0.0;
		double term1_2=0.0;
		double term2_1=0.0;
		double term2_2=0.0;
		
		term1_2= s.getP();
		term1_1= (term1_2-1)/(s.getN()*r+ (s.getN()-1)*l+ f*s.getN()+t);
		
		term2_2=_s1;
		term2_1= (term2_2-1)/(r+f+t); // Since s' first term has k=1
		
		if((term1_1< term2_1) &&(term1_2<term2_2))
			return true;
		else
			return false;
	}		
	
	public static boolean dMetricComparator(Node s, Node _s)
	{
		/**
		 * This method takes as parameters nodes S and _S. 
		 * It returns true if 
		 * 
		 */
	
		double term1_1=0.0;
		double term1_2=0.0;
		double term2_1=0.0;
		double term2_2=0.0;
		
		term1_1=_s.getN()*r+ (_s.getN()-1)*l+ f*_s.getN()+t;
		term1_2= _s.getP();
		
		// Assumed k=1 since we are considering only 1 term in s
		for(double p: s.getTerms())
		{
			term2_2= p;
			term2_1= r+f+t;
			 if(term1_1<term2_1 && term1_2<term2_2)
				 return true;
		}
		
		return false;
	}	
	
	public static boolean intersectionIsEmpty(Node s,Node _s)
	{
		/**
		 * This method takes as parameter- two nodes and returns true 
		 * if their intersection is empty.
		 */
		Iterator<Double> it= _s.names.keySet().iterator();
		Double term=0.0;
		
 		while(it.hasNext())
		{
			term=it.next();
			if(s.names.keySet().contains(term))
				return false;
		}
		
		return true;
	}
	
	public static int findUnionTerm(int s, int _s, int numOfSubset, Node A[])
	{
		/**
		 * This method takes two Nodes as parameter and returns the index of the node
		 * from the  major combination array A[] which contains the union of both 
		 * those nodes. 
		 */
		int index = -1;
		ArrayList<Double> allTerms= new ArrayList<Double>();
		
		allTerms.addAll(A[s].names.keySet());
		allTerms.addAll(A[_s].names.keySet());
		
		Set<Double> temp;
		
		
		for(int i=0; i<numOfSubset; i++)
		{
 			temp=A[i].names.keySet();
 			if(temp.containsAll(allTerms)&& temp.size()==allTerms.size())
 				{
 					index=i;
 					return index;
 				}
		}		
		
		return index;
	}
	
	public static double calcTempCost(Node s, Node _s)
	{		
		/**
		 * This method takes as parameter two nodes and calculates the cost
		 * for && operation for those two subsets.
		 * 
		 */
		double fcostE=s.getC();

		double q;
		double p= s.getP();
		
		q= p<(1-p)? p:(1-p);
		
		double C= _s.getC();
		double tempCost= fcostE+m*q+p*C;
		
		return tempCost ;
	}
	
	public static String printOptimalPlan(Node A[], int index)
	{
		/**
		 * This recursive method prints the optimal plan by accessing the 
		 * tree structure of the array.
		 * 
		 * The method call should be printOptimalPlan(A, numOfSubsets);
		 * 
		 */
		int L=0, R=0;
		if(A[index].getL()==-1)
			return ""+ A[index].printAll();
		else 
			{
			L= A[index].getL();
			R= A[index].getR();
			return ""+ printOptimalPlan(A, R)+ " && " + printOptimalPlan(A,L)+"";
			}
		
	}
	public static boolean checkLeftMostPlan(Node A[], int index)
	{
		/**
		 * This recursive method finds the leftmost plan and checks if it
		 * uses the no branch cost option by accessing the 
		 * tree structure of the array.
		 *  
		 */
		int L=0;
		if(A[index].getL()==-1)
			return A[index].isBit();
		else 
			{
			L= A[index].getL();
			return checkLeftMostPlan(A, L);
			}
		
	}
	
	public static void initHashMap(Node lastNode)
	{
		/**
		 * This method initializes the HashMap structure which maps the values to 
		 * term indexes.
		 * 
		 */
		
		Set<Double> tempSet= lastNode.names.keySet();
		ArrayList<Double> conversionList = new ArrayList<Double>();
		conversionList.addAll(tempSet);		
		ListIterator<Double> lt= conversionList.listIterator();
		int count=0;
		while(lt.hasNext())
		{
			lookUpMap.put(lt.next(), count+1);
			count++;
		}
		
	}
	
	public static void main(String[] args) {
		
		//double x=System.currentTimeMillis();
		
		// Step 1: Populate the productivities list with terms read from file
		File configFile = new File(args[1]);// config file
		File queryFile = new File(args[0]);// query file
		
		
		String line = "";
		try{			
			BufferedReader input =  new BufferedReader(new FileReader(queryFile));
			// read the file and form an ArrayList(doubles[])
			while((line=input.readLine())!=null){
				String[] values = line.split(" ");
				double val[] = new double[values.length];

					for(int i=0;i<values.length;i++){
						val[i] = Double.parseDouble(values[i]);

					}
					productivities.add(val);
				}
			input.close();
			// read the values and initialize into static variables.
			Properties p = new Properties();
			p.load(new FileInputStream(configFile));
			r=Double.parseDouble(p.getProperty("r").trim());
			t=Double.parseDouble(p.getProperty("t").trim());
			l=Double.parseDouble(p.getProperty("l").trim());
			m=Double.parseDouble(p.getProperty("m").trim());
			a=Double.parseDouble(p.getProperty("a").trim());
			f=Double.parseDouble(p.getProperty("f").trim());
			
		}catch(NumberFormatException nfe){
			System.out.println("Caught NFE while reading file "+nfe.getMessage());
			nfe.printStackTrace();
		}catch(Exception e){
			System.out.println(e);e.printStackTrace();
		}
		
		
	
		
		Main main = new Main();
		Iterator<double[]> it= productivities.iterator();
		double optimalCosts[]=new double[productivities.size()];
		
		while(it.hasNext())
		{
			leftMostPlan=true;
			currentArray= it.next();
			int count=0;
			k= currentArray.length;			
			numOfSubset= ((int) Math.pow(2, k))-1;
			Node A[]= new Node[numOfSubset];
			A=main.setA(currentArray, numOfSubset);
			
			System.out.println("======================================");
			for(Double d: currentArray)
					System.out.print(d.toString()+" ");
			
			System.out.println("\n--------------------------------------");
			
			//STEP 1: Initialization
			for(int i=0; i<numOfSubset; i++)
			{
				A[i].calculateP();
				A[i].calculateCost(r, t, l, m, a, f);
				
			}
			initHashMap(A[numOfSubset-1]);
			
			
			
			// STEP 2: Algorithm
			
			for(int s=0; s<numOfSubset; s++)
			{
				int _sus=0;
				double tempCost=0.0;
				
				for(int _s=0; _s<numOfSubset; _s++)
				{
					if(intersectionIsEmpty(A[s],A[_s]))
					{
						
						if(cMetricComparator(A[s],A[_s].terms.get(0)))
						{
							//do nothing
						}
						else if(A[_s].getP()<=0.5 && dMetricComparator(A[s], A[_s]))
						{
							//do nothing
							
						}
						else
						{
							
							
							_sus= findUnionTerm(s,_s,numOfSubset,A);
							
							tempCost= calcTempCost(A[_s],A[s]);
							
							if(A[_sus].getC()>tempCost)
								{
								
									A[_sus].setC(tempCost);
									A[_sus].setL(s);
									A[_sus].setR(_s);
									
								}
							
						}
					 
					}
				}
			}
			
			
			optimalCosts[count]= A[numOfSubset-1].getC();
			StringBuffer answer= new StringBuffer();
			
			// Extracting the nodes out of the tree structure
			String finalString=printOptimalPlan(A,numOfSubset-1);
			
			// Manipulating the generated String
			
			leftMostPlan=checkLeftMostPlan(A,numOfSubset-1);
			
			int tempIndex=finalString.lastIndexOf("&&");
				
				
			if(leftMostPlan){	
				if(tempIndex!=-1)
				{
				String tempString= finalString.substring(tempIndex);
				int andIndex= tempString.indexOf("t");
				andIndex= andIndex-1;
				int endIndex= tempString.lastIndexOf("]");
				endIndex=((endIndex+2)>tempString.length())? endIndex+1: endIndex+2;
				String initString= finalString.substring(0,tempIndex)+tempString.substring(endIndex);
				initString=initString.replace("&&", "&& (");
				
				
				int lastIndex = 0;
				int count1 =0;
				int count2=0;
				// counting opening brackets
				while(lastIndex != -1){
				
				lastIndex = initString.indexOf("(",lastIndex+1);
				if( lastIndex != -1)
						count1 ++;			
				}
				
				
				
				// counting ending brackets
				lastIndex=0;
				while(lastIndex != -1){
				lastIndex = initString.indexOf(")",lastIndex+1);
				if( lastIndex != -1){
				count2 ++;
									}
										}
				int xtemp=count1-count2;
				while(xtemp>0)
				{	
					
					initString+=")";
					xtemp--;
				}
				
				
				
				String endString=tempString.substring(andIndex, endIndex);
				
				
				answer.append("answer[j]=i;\n j+= "+ endString+";");
				System.out.println("if("+ initString+") {"+answer+"\n}");
				}
				else
				{		
					answer.append("answer[j]=i;\n j+= "+ finalString+";");
					System.out.println(answer);
					
				}
			}
			else
			{
				
				System.out.println("if("+ finalString+") {answer[j]=i;\n}");
			}
				
				System.out.println("--------------------------------------");
				
				System.out.println("Cost="+ optimalCosts[count]);
				count++;
			
		}
		
	}

}

